package arithmetic.demo16;

import java.util.*;


/**
 * 题目： BFS最短路径_单词接龙
 */

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 先判断是否有结果
        if (!wordList.contains(endWord))
            return 0;
        int ret = 1;
        // 长度
        int n = beginWord.length();

        Set<String> set = new HashSet<>();
        for (String s : wordList) {
            set.add(s);
        }
        Queue<String> queue = new LinkedList<>();

        // 定义一个哈希来去重
        Set<String> hash = new HashSet<>();
        queue.add(beginWord);
        hash.add(beginWord);

        // 进行 bfs
        while (!queue.isEmpty()) {
            // 对每一层累加次数
            ret++;
            int sz = queue.size();
            // 先得到当前层
            for (int i = 0; i < sz; i++) {
                String str = queue.poll();

                // 先遍历每一个字符串中的每一位
                for (int j = 0; j < n; j++) {
                    char[] tmp = str.toCharArray();
                    // 然后再将每一位上的字符的可能都进行更改
                    for (char k = 'a'; k <= 'z'; k++) {
                        tmp[j] = k;
                        String next = new String(tmp);
                        // 满足条件的进入队列
                        if (!hash.contains(next) && set.contains(next)) {
                            // 一旦想等就返回结果
                            if (next.equals(endWord)) {
                                return ret;
                            }
                            hash.add(next);
                            queue.add(next);
                        }
                    }
                }

            }


        }

        return 0;
    }
}

class Test {
    public static void main(String[] args) {
        List<String> wordList = new ArrayList<>();
        wordList.add("hot"); wordList.add("dog"); wordList.add("dot"); wordList.add("lot");
        wordList.add("log"); wordList.add("cog");
        Solution solution = new Solution();
        System.out.println(solution.ladderLength("hit", "cog", wordList));
    }
}


class Solution1 {
    public int cutOffTree(List<List<Integer>> forest) {
        int row = forest.size() , col = forest.get(0).size();
        Queue<Integer> queue= new LinkedList<>();
        queue.add(forest.get(0).get(0));

        return 1;
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        solution1.cutOffTree(new ArrayList<>());
    }
}


class Solution3 {
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    int row , col ;
    public int cutOffTree(List<List<Integer>> forest) {
        row = forest.size(); col = forest.get(0).size();
        // 建立小根堆
        PriorityQueue<Map.Entry<Integer, int[]>> priQueue =
                new PriorityQueue<>((a,b) -> {
                    return a.getKey() - b.getKey();
                });

        for(int i = 0; i< row ; i++) {
            for(int j = 0; j< col ; j++) {
                int num = forest.get(i).get(j);
                // 如果为 树就加入到大根堆
                if(num > 1) {
                    priQueue.add(Map.entry(num,new int[]{i,j}));
                }
            }
        }

        int ret = 0;
        int[] beginIndex = {0,0};

        // 记录每一层
        Queue<int[]> queue = new LinkedList<>();



        // 一步一步出较小的树
        while(!priQueue.isEmpty()) {

            Map.Entry<Integer, int[]> tmp = priQueue.poll();
            boolean[][] path = new boolean[row][col];

            // 目标下标和目标数据
            int[] aimIndex = tmp.getValue();
            int aim = tmp.getKey();
            int count = 0;

            // 先添加起始位
            queue.add(new int[]{beginIndex[0],beginIndex[1]});
            path[beginIndex[0]][beginIndex[1]] = true;

            boolean flg = false;
            // 开始搜索
            while(!queue.isEmpty()) {
                int sz = queue.size();
                ret++;

                // 先得到这几位
                while(sz-- != 0) {

                    int[] index= queue.poll();
                    // 进入节点
                    for(int k =0; k<4; k++) {
                        int x = index[0] + dx[k], y = index[1] + dy[k];
                        if(x >= 0 && x < row && y >= 0 && y < col
                                && !path[x][y] && forest.get(x).get(y) != 0) {

                            if(aim == forest.get(x).get(y)) {
                                // 用flg 记录当前是否找到
                                flg = true;
                                break;
                            }

                            // 添加下一层
                            queue.add(new int[]{x, y});
                            // 记录当前走过的位置
                            path[x][y] = true;
                        }
                    }

                }
            }

            // 如果没找到就返回 0;
            if(!flg) return 0;

            ret += count;
            // 将目标数组变成起始数组
            beginIndex = aimIndex;

        }

        return ret;
    }


}

class Test1 {
    public static void main(String[] args) {
        List<List<Integer>> forest = new ArrayList<>();
        int[] n1 = {1,2,3} , n2= {0,0,4}, n3 = {7,6,5};
        List<Integer> list1 = new ArrayList<>();
        list1.add(2); list1.add(3); list1.add(4);
        List<Integer> list2 = new ArrayList<>();
        list2.add(0); list2.add(0); list2.add(5);

        List<Integer> list3 = new ArrayList<>();
        list3.add(8); list3.add(7); list3.add(6);

        forest.add(list1); forest.add(list2) ; forest.add(list3);

        Solution2 solution2 = new Solution2();
        solution2.cutOffTree(forest);
    }
}

/**
 *
 * 题目: BFS最短路径_为高尔夫比赛砍树
 *
 */



class Solution2 {
    int row , col;
    int[] dx= {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    public int cutOffTree(List<List<Integer>> forest) {
        row = forest.size(); col = forest.get(0).size();
        // 先创建 一定顺序的下标
        List<int[]> tree = new ArrayList<>();
        for(int i = 0; i<row; i++) {
            for(int j = 0; j<col ; j++) {
                // 是树的就添加
                if(forest.get(i).get(j) > 1 ) {
                    tree.add(new int[]{i,j});
                }
            }
        }

        // 进行排序
        Collections.sort(tree, (a,b)->{
            return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
        });


        // 开始查找每一个
        int[] beginIndex = {0,0};
        int ret = 0;
        while(!tree.isEmpty()) {

            // 获取到最小的树
            int[] endIndex = tree.remove(0);
            int count = bfs(forest, beginIndex, endIndex) ;

            // 如果没找到就直接返回
            if(count == -1) return -1;

            // 累加每一次砍树需要走的步数
            ret += count;
            // 把前面的起始位置更新为目标位置
            beginIndex = endIndex;

        }


        return ret;

    }

    // 进行广度优先遍历
    public int bfs(List<List<Integer>> forest, int[] beginIndex , int[] endIndex) {
        int bx = beginIndex[0], by = beginIndex[1];
        int ex = endIndex[0], ey =endIndex[1];
        // 开始搜索
        Queue<int[]> queue = new LinkedList<>();
        // 标记走过的位置
        boolean[][] path = new boolean[row][col];


        // 初始化
        queue.add(new int[]{bx,by});
        int ret  = 0;
        path[bx][by] = true;

        while(!queue.isEmpty()) {
            int sz = queue.size();
            ret++;
            // 处理当层
            while(sz-- > 0 ) {
                // 当前位置
                int[] next = queue.poll();
                for(int k = 0; k < 4; k++) {
                    int m = next[0] + dx[k], n = next[1] + dy[k];
                    // 筛选符合要求的
                    if(m>= 0 && m < row && n >= 0 && n < col
                            && !path[m][n] && forest.get(m).get(n) != 0) {
                        // 判断是否是目标位置
                        if(m == ex && n == ey) {
                            return ret;
                        }

                        // 加入下一层
                        queue.add(new int[]{m,n});
                        // 标记当前位置
                        path[m][n] = true;
                    }
                }
            }
        }

        // 如果没有找到，直接返回 -1；
        return -1;
    }
}


/**
 * 题目： 多源BFS_01矩阵
 */

class Solution4 {
    int[] dx= {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int row , col;
    Queue<int[]> queue;
    int[][] ret ;
    public int[][] updateMatrix(int[][] mat) {
        queue  = new LinkedList<>();
        row = mat.length; col = mat[0].length;
        int[][] ret = new int[row][col];
        boolean[][] path = new boolean[row][col];


        // 正难则反， 把 0 当初起点， 1 当成终点

        for(int i = 0; i < row; i++) {
            for(int j = 0; j<col ; j++) {
                // 判断当前位置是否为 0
                if(mat[i][j] == 0) {
                    // 开始宽搜
                    // 初始化
                    queue.add(new int[]{i,j});
                    path[i][j] = true;
                }
            }
        }



        int step = 0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            step++;
            // 当前层数
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                for(int i =0; i<4; i++) {
                    int m = tmp[0] + dx[i];
                    int n = tmp[1] + dy[i];
                    // 判断条件
                    if(m >= 0 && m < row && n >= 0 && n < col && !path[m][n]) {
                        // 一旦找到就返回
                        if(mat[m][n] == 1) {
                            ret[m][n] = step;
                        }

                        // 加入下一层
                        queue.add(new int[]{m,n});
                        path[m][n] =  true;
                    }
                }
            }
        }

        return ret;

    }


}


/**
 * 题目： 多源bfs_飞地的数量
 */

class Solution5 {
    int[] dx = {0,0, 1, -1};
    int[] dy = {1,-1,0,0};
    public int numEnclaves(int[][] grid) {
        int row= grid.length, col = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] path = new boolean[row][col];

        // 寻找边界的 1
        for(int i = 0; i <row ; i++) {
            // 左边界
            if(grid[i][0] == 1) {
                queue.add(new int[]{i, 0});
                path[i][0] = true;
            }

            // 右边界
            if(grid[i][col-1] == 1) {
                queue.add(new int[]{i, col-1});
                path[i][col- 1] = true;
            }
        }


        for(int j = 0; j< col ; j++) {
            // 上边界
            if(grid[0][j] == 1) {
                queue.add(new int[]{0,j});
                path[0][j] = true;

            }

            // 下边界
            if(grid[row - 1][j] == 1) {
                queue.add(new int[]{row- 1,j});
                path[row - 1][j] = true;

            }
        }


        // 开始进行多源bfs
        while(!queue.isEmpty()) {
            int sz = queue.size();
            while(sz-- >  0) {
                // 得到这一层
                int[] tmp = queue.poll();
                for(int i =0; i<4 ; i++) {
                    int x = tmp[0] + dx[i], y = tmp[1] + dy[i];
                    if(x>= 0 && x < row && y >= 0 && y < col && !path[x][y] && grid[x][y] == 1) {
                        queue.add(new int[]{x,y});
                        path[x][y] = true;
                    }
                }
            }
        }


        // 搜索没有走过的 1
        int ret = 0;
        for(int i = 0 ; i< row ; i++) {
            for(int j = 0; j < col ; j++) {
                if(grid[i][j] == 1 && !path[i][j]) ret++;
            }
        }


        return ret;
    }
}


/**
 * 题目：多源BFS_地图中的最高点
 */


class Solution6 {
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    int row , col ;
    public int[][] highestPeak(int[][] isWater) {
        row = isWater.length; col = isWater[0].length;
        Queue<int[]> queue = new LinkedList<>();
        // 标记走过的路
        boolean[][] path = new boolean[row][col];

        int[][] ret = new int[row][col];

        // 把水洼处添加结果
        for(int i =0; i < row; i++) {
            for(int j = 0; j<col ; j++) {
                if(isWater[i][j] == 1) {
                    queue.add(new int[]{i,j});
                    path[i][j] = true;
                }
            }
        }


        while(!queue.isEmpty()) {
            // 遍历这层
            int sz=  queue.size();
            while(sz-- > 0) {
                int[] tmp =  queue.poll();
                for(int i =0;i< 4; i++) {
                    int x = tmp[0] + dx[i], y  = tmp[1] + dy[i];
                    // 进行下一层
                    if(x >= 0 && x < row &&   y >= 0 && y < col && !path[x][y] &&  isWater[x][y] != 1) {
                        // 在当前位置上进行 +1
                        ret[x][y] = ret[tmp[0]][tmp[1]] + 1;
                        // 并记录当前结果已经走过
                        path[x][y] = true;
                        // 并且添加到下一层
                        queue.add(new int[]{x,y});
                    }


                }
            }
        }


        return ret;

    }
}


/**
 * 题目：多源BFS_地图分析
 */

class Solution7 {
    int[] dx = { 0, 0, -1, 1 };
    int[] dy = { -1, 1, 0, 0 };

    public int maxDistance(int[][] grid) {
        int raw = grid.length, col = grid[0].length;
        boolean[][] path = new boolean[raw][col];
        int count = 0, ret = Integer.MIN_VALUE;

        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < raw; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    path[i][j] = true;
                    queue.add(new int[] { i, j });
                }
            }
        }


        if(queue.size() == 0 || queue.size() == raw * col) return -1;

        while (!queue.isEmpty()) {
            int sz = queue.size();
            count++;
            while (sz-- > 0) {
                int[] tmp = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int x = tmp[0] + dx[i], y = tmp[1] + dy[i];
                    if (x >= 0 && x < raw && y >= 0 && y < col && !path[x][y] && grid[x][y] == 0) {
                        queue.add(new int[] { x, y });
                        path[x][y] = true;
                    }
                }
            }
        }


        return count-1;
    }
}